/**
 * 插入排序
 * 空间复杂度:O(1)
 * 时间复杂度:O(n*n)
 * 算法稳定性:稳定
 */

#include <stdio.h>

void Insert_sort(int A[], int n);
void print(int a[], int n);

//带哨兵的插入排序
void Insert1_sort(int a[], int n);

int main()
{
	int a[10]={1,4,6,2,3,8,6,9,0,2};
	Insert_sort(a,10);
	return 0;
}

void Insert_sort(int A[], int n)
{
	print(A, n);
	printf("\n");
	
	int i,j,tmp;
	for(i=1;i<n;i++)	//将各元素插入到已经排好序的序列中
	{
		if(A[i]<A[i-1])		//若A[i]关键字小于前一个关键字
		{
			tmp=A[i];	//使用临时变量记录当前的A[i]
			for(j=i-1;j>=0 && A[j] > tmp;--j)	//从A[i]前面的元素一次往前找，如果找到小于A[i]就后移
				A[j+1]=A[j];
			A[j+1]=tmp;	//复制到插入位置
		}
	}
	print(A,10);
}


void print(int a[], int n)
{
	for(int i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
}

void Insert1_sort(int a[], int n)
{
	int i,j;
	for(i=2;i<n;i++)
	{
		if(a[i]<a[i-1])
		{
			a[0]=a[i];	//将a[i]元素复制到哨兵处a[0]
			for(j=i-1; a[0]<a[j];j--)//从第i处向前找比a[i]更小的元素，即比a[0]更小的元素
				a[j+1]=a[j];	//如果找到，j向后移动
			a[j+1]=a[j];
		}
	}
}